#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#define ELEMENTTYPE void *

typedef struct BinarySearchTreeNode
{
    /* 数据域 */
    ELEMENTTYPE  *data;

    /* 指针域 */
    struct BinarySearchTreeNode *left;
    struct BinarySearchTreeNode *right;
#if 1
    struct BinarySearchTreeNode * parent;//父结点
#endif
}BinarySearchTreeNode;

typedef struct BinarySearchTree
{
    /* 树元素个数 */
    int size;
    /* 树的高度 */
    int height;
    /* 根节点 */
    BinarySearchTreeNode *root;//拿到根结点才能拿到树

    /* 自定义打印器 */
    int (*printFunc)(ELEMENTTYPE arg);

    /* 自定义比较器 */
    int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2);
}BinarySearchTree;





// /* 树的初始化 */
// int bnarySearchTreeInit(BinarySearchTree **pTree);

/* 树的初始化 */
int binarySearchTreeInit(BinarySearchTree **pTree,  int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2), int (*printFunc)(ELEMENTTYPE arg));

/* 树的插入  */
int bnarySearchTreeInsert(BinarySearchTree *pTree, ELEMENTTYPE data);

//静态声明
static int bnarySearchTreeInnerPreOrder(BinarySearchTree *pTree, BinarySearchTree *travelNode);

/* 树的前序遍历 */
int bnarySearchTreePreOrder(BinarySearchTree *pTree);

/* 树的中序遍历 */
int bnarySearchTreeInOrder(BinarySearchTree *pTree);

/* 树的后序遍历 */
int bnarySearchTreePosOrder(BinarySearchTree *pTree);

/* 树的层序遍历 */
int bnarySearchTreeOrder(BinarySearchTree *pTree);

/* 树的高度 */
int bnarySearchTreeGetheight(BinarySearchTree *pTree, int *pHeight);

/* 销毁*/
int bnarySearchTreeDestroy(BinarySearchTree *pTree);

/* 树的删除 */
int bnarySearchTreeDelete(BinarySearchTree *pTree, ELEMENTTYPE data);

/* 树是否存在该元素值 */
int bnarySearchTreeIsContainVa(BinarySearchTree *pTree, ELEMENTTYPE data);


#endif
